The present invention relates to a method and apparatus useful for coding and decoding images such as line drawings that comprise mostly background area.
Black-and-white bi-level images can be encoded by run-length coding, which encodes the number of consecutive picture elements or pixels having the same value. When this type of image is transmitted by facsimile, for example, the image is scanned a line at a time, and each scanning line is encoded as run lengths specifying the relative positions of the pixels at which a change from black to white, or from white to black, occurs. In the modified Huffman (MH) code adopted in group-three facsimile equipment, the run-length information is further coded by use of variable-length coding tables, using different tables for black runs and white runs, because the two types of runs have different statistical properties.
When this type of run-length coding is applied to an image comprising mostly white background area, however, most of the coded data is used to encode long runs of background pixels. Variable-length coding of the background in this type of image is inefficient, because the variable-length coding rule forces the use of many redundant bits. If the redundancy could be reduced, higher data compression ratios could be obtained.
More efficient coding schemes, such as arithmetic coding, are known, but they tend to be computationally demanding in terms of program complexity, memory usage, and processing time.
The above problems are not limited to bi-level images, but also occurs in other types of sparse images, including images that employ several colors, or multiple shades of gray. These problems moreover occur not only in facsimile transmission, but also in image storage and retrieval, and in the transmission of image data from a computer to a printer.